package com.回溯法寻找矩阵中的路径;

/*
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 * 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
 * 如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 
 * 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，
 * 但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，
 * 路径不能再次进入该格子。
 * */
public class Again {
	public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
		boolean[] visited=new boolean[rows*cols];
		for(int r = 0;r<rows;r++) {
			for(int c=0;c<cols;c++) {
				if(findpath(matrix, rows, cols, r, c, str,0, visited)) {
					return true;
				}
			}
		}
		return false;

	}
	public boolean findpath(char[] matrix,int rows,int cols,int r,int c,char[]str,int index,boolean[] visited) {
		if(r<0||r>=rows||c<0||c>=cols||visited[r*cols+c]||matrix[r*cols+c]!=str[index])return false;
		visited[r*cols+c]=true;
		if(index==str.length-1)return true;
		if(findpath(matrix, rows, cols, r+1, c, str, index+1, visited)||
		   findpath(matrix, rows, cols, r-1, c, str, index+1, visited)||
		   findpath(matrix, rows, cols, r, c+1, str, index+1, visited)||
		   findpath(matrix, rows, cols, r, c-1, str, index+1, visited)) {
			//只要上下左右有合适的点那么久返回true
			return true;
			
		}
		visited[r*cols+c]=false;
		return false;
		
	}
}
